﻿#include <iostream>

// leetcode

// 724.寻找数组的中心下标

class Solution
{
public:
    int pivotIndex(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> bp1(n), bp2(n);
        for (int i = 1; i < n; i++)
            bp1[i] = bp1[i - 1] + nums[i - 1];
        for (int i = n - 2; i >= 0; i--)
            bp2[i] = bp2[i + 1] + nums[i + 1];
        for (int i = 0; i < n; i++)
        {
            if (bp1[i] == bp2[i])
                return i;
        }
        return -1;
    }
};

// 数学法
// 记数组的全部元素之和为 total，当遍历到第 i 个元素时，
// 设其左侧元素之和为 sum，则其右侧元素之和为 total−nums i−sum
// 左右侧元素相等即为 sum=total−nums i−sum，即 2×sum+nums i=total
class Solution
{
public:
    int pivotIndex(vector<int>& nums)
    {
        int total = accumulate(nums.begin(), nums.end(), 0);
        int sum = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (2 * sum + nums[i] == total)
                return i;
            sum += nums[i];
        }
        return -1;
    }
};


// 清晰的前缀和

class Solution
{
public:
    int pivotIndex(vector<int>& nums)
    {
        int sumleft = 0, sumright = accumulate(nums.begin(), nums.end(), 0);
        for (int i = 0; i < nums.size(); i++)
        {
            sumright -= nums[i];
            if (sumleft == sumright)
                return i;
            sumleft += nums[i];
        }
        return -1;
    }
};



// 238.除自身以外数组的乘积

class Solution
{
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> mulleft(n), mulright(n);
        mulleft[0] = mulright[n - 1] = 1;
        for (int i = 1; i < n; i++)
            mulleft[i] = mulleft[i - 1] * nums[i - 1];
        for (int i = n - 2; i >= 0; i--)
            mulright[i] = mulright[i + 1] * nums[i + 1];
        vector<int> ans;
        for (int i = 0; i < n; i++)
            ans.push_back(mulleft[i] * mulright[i]);

        return ans;
    }
};



// 560.和为K的子数组

class Solution
{
public:
    int subarraySum(vector<int>& nums, int k)
    {
        unordered_map<int, int> hash;
        hash[0] = 1;// 初始化：前缀和为0的次数为1（空子数组）
        int sum = 0, ans = 0;
        for (auto& e : nums)
        {
            sum += e;
            if (hash.count(sum - k))// 检查是否存在前缀和 sum - k
                ans += hash[sum - k]; // 存在则更新答案
            hash[sum]++;// 记录当前前缀和的出现次数
        }

        return ans;
    }
};




// 974.和可被K整除的子数组

class Solution
{
public:
    int subarraysDivByK(vector<int>& nums, int k)
    {
        int sum = 0, ans = 0;
        unordered_map<int, int> hash;
        hash[0 % k] = 1;
        for (auto& e : nums)
        {
            sum += e;
            int tep = (sum % k + k) % k; // 取正值
            if (hash.count(tep))
                ans += hash[tep % k];
            hash[tep]++;
        }

        return ans;
    }
};


